"""
@author: 景云鹏
@email: 310491287@qq.com
@date: 2022/6/12
"""
from typing import List


class Solution:
    def __init__(self):
        self.index = None
        self.s = None

    def init(self, s: str):
        self.s = s
        self.index = [1 << i for i in range(len(s) - 2, -1, -1)]

    def partition(self, s: str) -> List[List[str]]:
        self.init(s)
        result = []
        for num in self.sub(0):
            cur = []
            last_cut = 0
            cur_cut = 0
            while num != 0:
                while num < self.index[cur_cut]:
                    cur_cut += 1
                num -= self.index[cur_cut]
                cur_cut += 1
                cur.append(s[last_cut: cur_cut])
                last_cut = cur_cut
            cur.append(s[cur_cut:])
            result.append(cur)
        return result

    def sub(self, start: int):
        nums = []
        for first_cut in self.first_cuts(start):
            if first_cut == len(self.s):
                nums.append(0)
            else:
                cur = self.index[first_cut - 1]
                for num in self.sub(first_cut):
                    nums.append(cur + num)
        return nums

    def first_cuts(self, start):
        cuts = [start + 1]
        for j in range(start + 1, len(self.s)):
            if self.check_palindrome(start, j):
                cuts.append(j + 1)
        return cuts

    def check_palindrome(self, start, end):
        while start < end:
            if self.s[start] != self.s[end]:
                return False
            start += 1
            end -= 1
        else:
            return True


